Inégalité de Kraft

Inégalité de Kraft

Si $c$ est un code binaire instantané, alors $$\sum_{x\in\mathcal X}2^{-l_c(x)}\leqslant1$$
Si $l_1,\dots,l_M$ sont $M$ entiers qui vérifient $$\sum^M_{i=1}2^{-l_i}\leqslant1$$ alors il existe un Code instantané binaire de $M$ mots qui satisfait ces longueurs

la même chose existe pour les Code déchiffrables : c'est l'inégalité de McMillan

Démontrer $(1)$ :

Le caractère instantané (et donc la non singularité) nous permet de supposer que le nombre de mots du dictionnaire est égal au cardinal de l'alphabet.

On note $N_j$ le nombre de mots de longueur $j$, de manière à ce que la somme des $N_j$ soit $M$.

Pour démontrer l'inégalité, on va majorer chacun des termes, i.e. Majorer le nombre maximal de mots de longueur $j$, pour tout $j$.

On réfléchit d'abord avec les petits indices $\to$ le cas $j=1$ est simple.

Pour $j=2$, $N_2$ dépend de $N_1$.

Cette étude peut être résumée par une formule, qui majore $N_2$ en utilisant $N_1$.

Idem pour $j=3$, il faut considérer $N_2$ et $N_1$, ce qui donne une majoration similaire.

En procédant par récurrence, on a alors une majoration de $N_m$ qui dépend de tous les $N_j$ précédents.

La majoration prend une forme qui nous intéresse plus lorsqu'on divise par $2^m$ des deux côtés.

10: On retrouve la majoration recherchée en passant des $N_j$ aux $l_i$ (en réorganisant les termes de la somme).

'information

Math'φsics

Formulaire de report